package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.LinkedList;

public class LargestRectangleInHistogram {

    /**
     * 单调栈 + 哨兵
     */
    public int largestRectangleArea(int[] heights) {
        int m = heights.length, n = m + 2;
        int maxArea = 0;
        int[] newHeights = new int[n];
        // 为柱子两边添加为0的哨兵, 运用哨兵可以避免非空判断和尾部计算
        System.arraycopy(heights, 0, newHeights, 1, m);

        LinkedList<Integer> stack = new LinkedList<>();
        // 将哨兵压入栈
        stack.push(0);
        for (int i = 1; i < n; ++i){
            // 判断栈中是否有高于当前柱子的柱子，然后计算柱子中矩形的面积
            // 如果有高于的柱子，说明 i 就是矩形右边的柱子，栈顶的柱子就是矩形的高度，栈顶下面的下标就是矩形左边的柱子
            while ((newHeights[stack.getFirst()] > newHeights[i])){
                int h = newHeights[stack.pop()];
                int left = stack.getFirst() + 1;
                int right = i - 1;
                maxArea = Math.max((right - left + 1) * h, maxArea);
            }
            stack.push(i);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2,1, 2};
        int i = new LargestRectangleInHistogram().largestRectangleArea(heights);
        System.out.println(i);
    }
}
